TNotes.leetcode

Appearance

0541. 反转字符串 II【简单】

0541. 反转字符串 II【简单】 ​

1. 📝 题目描述 ​

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

txt
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

txt
输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 10^4
  • s 仅由小写英文组成
  • 1 <= k <= 10^4

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function (s, k) {
  // 将字符串转换为数组，便于操作
  const arr = s.split('')
  const n = arr.length

  // 每 2k 个字符为一组进行处理
  for (let i = 0; i < n; i += 2 * k) {
    // 确定需要反转的范围
    let left = i
    let right = Math.min(i + k - 1, n - 1)

    // 反转指定范围内的字符
    while (left < right) {
      ;[arr[left], arr[right]] = [arr[right], arr[left]]
      left++
      right--
    }
  }

  return arr.join('')
}
js
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function (s, k) {
  let result = ''

  for (let i = 0; i < s.length; i += 2 * k) {
    // 取出当前组
    const group = s.substring(i, i + 2 * k)

    // 反转前k个字符
    const toReverse = group.substring(0, k).split('').reverse().join('')

    // 拼接结果：反转部分 + 剩余部分
    result += toReverse + group.substring(k)
  }

  return result
}
  • 时间复杂度：O(n)，其中 n 是字符串的长度，需要遍历每个字符一次
  • 空间复杂度：O(n)，需要额外的数组存储字符
  • 算法思路：
    1. 分组处理：每 2k 个字符为一组进行处理
    2. 按规则反转：
      • 反转每组的前 k 个字符
      • 如果剩余字符不足 k 个，全部反转
      • 如果剩余字符在 [k, 2k) 范围内，只反转前 k 个
    3. 拼接结果：将处理后的各段拼接成最终结果
  • js-2 采用的是切片的实现方式，解题思路跟 js-1 是一样的。
  • 执行过程示例：
txt
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"

n = 7, k = 2, 2k = 4

处理过程：
i = 0: 处理 [0, 3] 范围
  - 反转前 k=2 个字符 [0, 1]："ab" -> "ba"
  - 结果："bacd" + "efg"

i = 4: 处理 [4, 6] 范围（剩余3个字符）
  - 反转前 k=2 个字符 [4, 5]："ef" -> "fe"
  - 结果："bacd" + "feg" = "bacdfeg"
txt
示例 2：
输入：s = "abcd", k = 2
输出："bacd"

n = 4, k = 2, 2k = 4

处理过程：
i = 0: 处理 [0, 3] 范围（正好2k个字符）
  - 反转前 k=2 个字符 [0, 1]："ab" -> "ba"
  - 剩余字符 "cd" 保持不变
  - 结果："bacd"

Discussions